java获取所有唯一的子字符串
我正在编写一个程序,该程序计算给定输入字符串的所有可能的不同连续子字符串
这是我的节目:
public int getAllUniqueSubset(String str) {
Set<String> set = new HashSet<String>();
for (int i = 0; i < str.length(); i++) {
for (int j = 0; j < str.length() - i; j++) {
String elem = str.substring(j, j + (i+1));
if (!set.contains(elem)) {
set.add(elem);
}
}
}
return set.size();
}
几天前,当我在一次在线考试中使用它时,由于输入字符串长度可能高达10次方5,导致超时错误而失败
在这篇文章中也有类似的问题-{a1}我也用了同样的答案
解决这个问题的正确方法是什么
# 1 楼答案
不过,有些想法可能不足以解决您的可伸缩性问题:
您不需要
if (!set.contains(elem))
检查,因为这已经在set.add()
方法的逻辑中了。这需要一些时间来检查(即使是常数)您可能希望将集合更改为列表(即使这涉及更大的空间消耗),并在最后转换为集合,以删除重复项
似乎有些计算可以并行进行(例如,分配给一个工人执行长度为1的子串,分配给另一个长度为2的子串,等等)。这些不需要交叉检查(即,不需要检查每个工人的结果是否重复)。例如,您可以尝试多线程或Spark(如果并行化开销没有更大的话)
# 2 楼答案
字符串长度10^5假设二次解太慢。生成所有n^2个子字符串并计算它们的哈希值,因此总时间是立方的,超时是可以预期的
相反,您可以在O(nlogn)时间内构建后缀数组,然后使用Kasai方法或其他算法构建LCP(最长公共前缀)
我们可以看到,每个后缀
p[i]
都有长度n - p[i]
,并产生n - p[i]
前缀作为子字符串。但是lcp[i-1]
前缀与前一个后缀的前缀重合!因此,对于每个后缀,我们只有n - p[i] - lcp[i-1]
个新的inique子字符串。通过siffixes获得O(n)时间内不同子字符串的计数总的时间是
# 3 楼答案
从GeeksForGeeks尝试这个解决方案